package ch4.section8;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 编写一个程序可以找出通过单个字母的替换可以变成至少15个其他单词的单词
 */
public class Test {

    /**
     * 给出包含一些单词作为关键字和只在一个字母上不同的一列单词作为关键字的值，输出那些具有minWords个或更多个通过1个字母替换得到的单词的单词
     *
     * @param adjWords
     * @param minWords
     */
    public static void printHighChangeables(Map<String, List<String>> adjWords, int minWords) {
        for (Map.Entry<String, List<String>> entry : adjWords.entrySet()) {
            List<String> words = entry.getValue();
            if (words.size() >= minWords) {
                System.out.println(entry.getKey() + "(");
                System.out.println(words.size() + "):");
                for (String w : words) {
                    System.out.println(" " + w);
                }
                System.out.println();
            }
        }
    }

    /**
     * 检测两个单词是否只在一个字母上不同的例程
     *
     * @param word1
     * @param word2
     * @return
     */
    private static boolean oneCharOff1(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        int diffs = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                if (++diffs > 1) {
                    return false;
                }
            }
        }

        return diffs == 1;
    }

    private static boolean oneCharOff2(String word1, String word2) {
//        if (word1.length() != word2.length()) {
//            return false;
//        }
        int diffs = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                if (++diffs > 1) {
                    return false;
                }
            }
        }

        return diffs == 1;
    }

    /**
     * 计算合适的单词
     * 计算一个Map对象的函数，该对象以一些单词作为关键字而已只在一个字母处不同的一列单词作为关键字的值，该函数对一个89000单词的词典运行75秒
     *
     * @param theWords
     * @return
     */
    public static Map<String, List<String>> computeAdjacentWords1(List<String> theWords) {
        Map<String, List<String>> adjWords = new TreeMap<>();
        String[] words = new String[theWords.size()];
        theWords.toArray(words);//把集合转存到一个数组里面
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (oneCharOff1(words[i], words[j])) {
                    update(adjWords, words[i], words[j]);
                    update(adjWords, words[j], words[i]);
                }
            }
        }
        return adjWords;
    }

    /**
     * 计算一个映射函数，该映射以单词作为关键字并且以只有一个字母不同的一列单词作为关键字的值。将单词按照长度分组。该算法对89000个单词的词典运行16秒。
     * @param theWords
     * @return
     */
    public static Map<String, List<String>> computeAdjacentWords2(List<String> theWords) {
        Map<String, List<String>> adjWords = new TreeMap<>();
        Map<Integer, List<String>> wordsByLength = new TreeMap<>();

        //Group the words by their length
        for (String w : theWords) {
            update(wordsByLength, w.length(), w);
        }

        //Work on each group separately
        for (List<String> groupsWrods : wordsByLength.values()) {
            String[] words = new String[groupsWrods.size()];
            groupsWrods.toArray(words);
            for (int i = 0; i < words.length; i++) {
                for(int j = i+1; j < words.length; j++ ){
                    if(oneCharOff2(words[i],words[j])){
                        update(adjWords,words[i],words[j]);
                        update(adjWords,words[j],words[i]);
                    }
                }
            }
        }
        return adjWords;
    }

    //计算包含单词作为关键字以及只有一个字母不同
    public static Map<String,List<String>> computeAdjacentWords3(List<String> words){
        TreeMap<String,List<String>> adjWords = new TreeMap<>();
        TreeMap<Integer,List<String>> wordsByLength = new TreeMap<>();

        //Group the words by their lenght
        for(String w : words){
            update(wordsByLength,w.length(),w);
        }

        //Work on each group separately
        for(Map.Entry<Integer,List<String>> entry : wordsByLength.entrySet()){
            List<String> groupsWords = entry.getValue();
            int groupNum = entry.getKey();

            //Work on each position in each group
            for(int i = 0;i < groupNum; i++){
                // Remove one character in specified position,computing
                // representative. Words with same represnetative are
                // adjacent,so first populate a map
                Map<String,List<String>> repToWord = new TreeMap<>();

                for(String str : groupsWords){
                    String rep = str.substring(0, i) + str.substring(i + 1);
                    update(repToWord,rep,str);
                }

                //and then look for map values with more than one string
                for(List<String> wordClique : repToWord.values()){
                    if(wordClique.size() >= 2){
                        for(String s1 : wordClique){
                            for(String s2 : wordClique){
                                if(s1 != s2){
                                    update(adjWords,s1,s2);
                                }
                            }
                        }
                    }
                }
            }

        }

        return adjWords;
    }



    private static <KeyType> void update(Map<KeyType, List<String>> m, KeyType key, String value) {
        List<String> lst = m.get(key);
        if (lst == null) {
            lst = new ArrayList<>();
            m.put(key, lst);
        }
        lst.add(value);
    }

}
